#pragma once

#include <unordered_map>
#include <list>
#include <mutex>
#include <memory>
#include <functional>

/*
 * 缓存淘汰策略 - 最不常用LFU(Least Frequently Used);
 * 每次访问(读/写)一个元素, 都记录使用次数。
 * 当缓存满了, 淘汰使用次数最少且最久未使用的元素;
 */

/**
 * @brief Thread-safe LFU (Least Frequently Used) Cache template
 *
 * This template provides a generic LFU cache implementation with the following features:
 * - Thread-safe operations using mutex
 * - Configurable capacity with automatic eviction
 * - O(1) average get, put, and remove operations
 * - Optional eviction callback for cleanup
 * - Uses frequency-based eviction: least frequently used items are removed first
 * - On frequency tie, most recently accessed among same frequency is kept at front
 *
 * @tparam Key The key type (must be hashable)
 * @tparam Value The value type
 */
template <typename Key, typename Value>
class LFUCache
{
public:
    using key_type = Key;
    using value_type = Value;
    using eviction_callback_t = std::function<void(const Key &, const Value &)>;

private:
    // Node structure storing key, value, and access frequency
    struct Node
    {
        Key key;
        Value value;
        size_t freq;

        Node(const Key &k, const Value &v, size_t f) :
            key(k), value(v), freq(f)
        {
        }
    };

    using node_list_t = std::list<Node>;
    using node_iterator_t = typename node_list_t::iterator;
    using key_map_t = std::unordered_map<Key, node_iterator_t>; // key -> node node_iterator_t
    using freq_map_t = std::unordered_map<size_t, node_list_t>; // freq -> list of nodes

public:
    /**
     * @brief Construct LFUCache with specified capacity
     * @param capacity Maximum number of items to cache (default: 100)
     */
    explicit LFUCache(size_t capacity = 100) :
        capacity_(capacity), min_freq_(0)
    {
        if (capacity_ == 0)
        {
            capacity_ = 1; // Minimum capacity of 1
        }
    }

    /**
     * @brief Destructor
     */
    virtual ~LFUCache()
    {
        clear();
    }

    // Disable copy constructor and assignment operator
    LFUCache(const LFUCache &) = delete;
    LFUCache &operator=(const LFUCache &) = delete;

    /**
     * @brief Set eviction callback function
     * @param callback Function to call when items are evicted
     */
    void set_eviction_callback(eviction_callback_t callback)
    {
        std::lock_guard<std::mutex> lock(mutex_);
        eviction_callback_ = callback;
    }

    /**
     * @brief Get value by key
     * @param key The key to search for
     * @param value Output parameter for the value
     * @return true if key exists, false otherwise
     */
    bool get(const Key &key, Value &value)
    {
        std::lock_guard<std::mutex> lock(mutex_);
        auto it = key_map_.find(key);
        if (it == key_map_.end())
        {
            return false;
        }

        touch(it->second);
        value = it->second->value;
        return true;
    }

    /**
     * @brief Get value by key (pointer interface)
     * @param key The key to search for
     * @return Pointer to value if exists, nullptr otherwise
     */
    Value *get(const Key &key)
    {
        std::lock_guard<std::mutex> lock(mutex_);
        auto it = key_map_.find(key);
        if (it == key_map_.end())
        {
            return nullptr;
        }

        touch(it->second);
        return &(it->second->value);
    }

    /**
     * @brief Put key-value pair into cache
     * @param key The key
     * @param value The value
     * @return true if new item was added, false if existing item was updated
     */
    bool put(const Key &key, const Value &value)
    {
        std::lock_guard<std::mutex> lock(mutex_);

        auto it = key_map_.find(key);
        if (it != key_map_.end())
        {
            // Update existing entry
            touch(it->second);
            it->second->value = value;
            return false;
        }

        // Insert new entry
        if (key_map_.size() >= capacity_)
        {
            evict_lfu();
        }

        // Add new node with frequency 1
        freq_map_[1].emplace_front(Node(key, value, 1));
        key_map_[key] = freq_map_[1].begin();
        min_freq_ = 1; // New item has freq=1, so min_freq resets to 1
        return true;
    }

    /**
     * @brief Remove item by key
     * @param key The key to remove
     * @return true if item was removed, false if not found
     */
    bool remove(const Key &key)
    {
        std::lock_guard<std::mutex> lock(mutex_);
        auto it = key_map_.find(key);
        if (it == key_map_.end())
        {
            return false;
        }

        const Node &node = *(it->second);
        freq_map_[node.freq].erase(it->second);
        if (freq_map_[node.freq].empty())
        {
            freq_map_.erase(node.freq);
            if (min_freq_ == node.freq)
            {
                min_freq_++;
            }
        }

        if (eviction_callback_)
        {
            eviction_callback_(node.key, node.value);
        }

        key_map_.erase(it);
        return true;
    }

    /**
     * @brief Check if key exists in cache
     * @param key The key to check
     * @return true if key exists, false otherwise
     */
    bool contains(const Key &key) const
    {
        std::lock_guard<std::mutex> lock(mutex_);
        return key_map_.find(key) != key_map_.end();
    }

    /**
     * @brief Clear all items from cache
     */
    void clear()
    {
        std::lock_guard<std::mutex> lock(mutex_);
        if (eviction_callback_)
        {
            for (const auto &freq_list : freq_map_)
            {
                for (const Node &node : freq_list.second)
                {
                    eviction_callback_(node.key, node.value);
                }
            }
        }
        key_map_.clear();
        freq_map_.clear();
        min_freq_ = 0;
    }

    /**
     * @brief Get current cache size
     * @return Number of items in cache
     */
    size_t size() const
    {
        std::lock_guard<std::mutex> lock(mutex_);
        return key_map_.size();
    }

    /**
     * @brief Get cache capacity
     * @return Maximum number of items cache can hold
     */
    size_t capacity() const
    {
        return capacity_;
    }

    /**
     * @brief Check if cache is empty
     * @return true if cache is empty, false otherwise
     */
    bool empty() const
    {
        std::lock_guard<std::mutex> lock(mutex_);
        return key_map_.empty();
    }

    /**
     * @brief Set new capacity (may trigger eviction)
     * @param new_capacity New capacity value
     */
    void set_capacity(size_t new_capacity)
    {
        if (new_capacity == 0)
        {
            new_capacity = 1; // Minimum capacity of 1
        }

        std::lock_guard<std::mutex> lock(mutex_);
        capacity_ = new_capacity;

        // Evict excess items if necessary
        while (key_map_.size() > capacity_)
        {
            evict_lfu();
        }
    }

    /**
     * @brief Apply a function to all cached items (for iteration)
     * Note: Iteration order is unspecified due to frequency buckets.
     */
    template <typename Func>
    void for_each(Func func)
    {
        std::lock_guard<std::mutex> lock(mutex_);
        for (const auto &bucket : freq_map_)
        {
            for (const Node &node : bucket.second)
            {
                func(node.key, node.value);
            }
        }
    }

    /**
     * @brief Remove items that match a predicate
     * @param predicate Function returning true for items to remove
     * @return Number of items removed
     */
    template <typename Predicate>
    size_t remove_if(Predicate predicate)
    {
        std::lock_guard<std::mutex> lock(mutex_);
        size_t removed_count = 0;
        auto freq_it = freq_map_.begin();
        while (freq_it != freq_map_.end())
        {
            auto &lst = freq_it->second;
            auto node_it = lst.begin();

            while (node_it != lst.end())
            {
                if (predicate(node_it->key, node_it->value))
                {
                    if (eviction_callback_)
                    {
                        eviction_callback_(node_it->key, node_it->value);
                    }
                    key_map_.erase(node_it->key);
                    node_it = lst.erase(node_it);
                    ++removed_count;
                }
                else
                {
                    ++node_it;
                }
            }

            if (lst.empty())
            {
                freq_it = freq_map_.erase(freq_it);
            }
            else
            {
                ++freq_it;
            }
        }

        if (freq_map_.empty())
        {
            min_freq_ = 0;
        }
        else
        {
            min_freq_ = std::numeric_limits<size_t>::max();
            for (const auto &bucket : freq_map_)
            {
                if (!bucket.second.empty())
                {
                    min_freq_ = std::min(min_freq_, bucket.first);
                }
            }
        }

        return removed_count;
    }

private:
    /**
     * @brief Update frequency: move node from freq to freq+1
     * @param node_it Iterator to the node being accessed
     */
    void touch(node_iterator_t node_it)
    {
        const size_t freq = node_it->freq;

        // Move the node from current frequency list to freq+1 list, at front
        auto &next_list = freq_map_[freq + 1];
        next_list.splice(next_list.begin(), freq_map_[freq], node_it);
        node_it->freq = freq + 1;
        // Update key_map to point to the new valid iterator (it remains valid after splice)
        // key_map_[node_it->key] = node_it;

        if (freq_map_[freq].empty())
        {
            freq_map_.erase(freq);
            if (min_freq_ == freq)
            {
                min_freq_++;
            }
        }
    }

    /**
     * @brief Evict the least frequently used item
     */
    void evict_lfu()
    {
        auto it = freq_map_.find(min_freq_);
        if (it == freq_map_.end())
        {
            return;
        }

        // The least recently used among min frequency is at the back
        auto &list = it->second;
        auto &last_node = list.back();

        // Call eviction callback
        if (eviction_callback_)
        {
            eviction_callback_(last_node.key, last_node.value);
        }

        key_map_.erase(last_node.key);
        it->second.pop_back();

        if (it->second.empty())
        {
            freq_map_.erase(min_freq_);
            min_freq_++;
        }
    }

private:
    size_t capacity_;
    mutable std::mutex mutex_;

    size_t min_freq_;     // Current minimum frequency
    key_map_t key_map_;   // key -> node_iterator_t to node
    freq_map_t freq_map_; // frequency -> list of nodes (ordered by recency)
    eviction_callback_t eviction_callback_;
};